package 算法.leetcode.labuladong.数组和链表;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author lchenglong
 * @date 2022/6/21
 */
public class 跳跃游戏VI {
    static class Solution {
        public static void main(String[] args) {
            int[] nums = new int[]{1,-5,-3,-7,3};
            Solution solution = new Solution();
            int ans = solution.maxResult(nums, 3);
            System.out.println(ans);
        }
        public int maxResult(int[] nums, int k) {
            Deque<int[]> deque = new ArrayDeque<>();
            // base case
            deque.offerFirst(new int[]{nums[0],0});
            int ans = nums[0];
            for (int i = 1;i<nums.length;i++) {
                // 对首j不满足单调性
                while (i-deque.peekFirst()[1]>k){
                    deque.pollFirst();
                }
                ans = deque.peekFirst()[0] + nums[i];
                // 队尾的j不满足单调性
                while (!deque.isEmpty() &&ans >= deque.getLast()[0]){
                    deque.pollLast();
                }
                deque.offerLast(new int[]{ans,i});
            }
            return ans;
        }


    }
}
